## Основные структуры данных


<details>
<summary>
<strong>Мониторинг</strong>
</summary><br>

[`Решение`](/sprint_2/1_monitoring.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/A/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107657161/)

```
Алла получила задание, связанное с мониторингом работы различных серверов. 
Требуется понять, сколько времени обрабатываются определённые запросы на 
конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца 
соответствуют идентификатору запроса, а номер строки — идентификатору сервера. 
Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей 
исправить баг.
Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.
Транспонированная матрица получается из исходной заменой строк на столбцы.
```
#### Формат ввода
```
В первой строке задано число n — количество строк матрицы.
Во второй строке задано m — число столбцов, m и n не превосходят 1000. 
В следующих n строках задана матрица. Числа в ней не превосходят 
по модулю 1000.
```

#### Формат вывода
```
Напечатайте транспонированную матрицу в том же формате, который задан во 
входных данных. Каждая строка матрицы выводится на отдельной строке, 
элементы разделяются пробелами.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        4<br>
        3<br>
        1 2 3<br>
        0 2 6<br>
        7 4 1<br>
        2 7 0<br>
    </td>
    <td valign="top">
        1 0 7 2<br>
        2 2 4 7<br>
        3 6 1 0<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Список дел</strong>
</summary><br>

[`Решение`](/sprint_2/2_todosList.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/B/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107657965/)
```
Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите 
функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать 
только функцию, которая принимает на вход голову списка и печатает его 
элементы. Ниже дано описание структуры, которая задаёт узел списка.
```
#### Формат ввода
```
В качестве ответа сдайте только код функции, которая печатает элементы списка. 
Длина списка не превосходит 5000 элементов. Список не бывает пустым.
```
#### Формат вывода
```
Функция должна напечатать элементы списка по одному в строке.
```
</details>

---

<details>
<summary>
<strong>Нелюбимое дел</strong>
</summary><br>

[`Решение`](/sprint_2/3_unfavoriteJob.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/C/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107660350/) |
```
Вася размышляет, что ему можно не делать из того списка дел, который он 
составил. Но, кажется, все пункты очень важные! Вася решает загадать число и 
удалить дело, которое идёт под этим номером. Список дел представлен в виде 
односвязного списка. Напишите функцию solution, которая принимает на вход 
голову списка и номер удаляемого дела и возвращает голову обновлённого списка.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать 
только функцию, которая принимает на вход голову списка и номер удаляемого 
элемента и возвращает голову обновлённого списка.
```
#### Формат ввода
```
Функция принимает голову списка и индекс элемента, который надо удалить 
(нумерация с нуля). Список содержит не более 5000 элементов. 
Список не бывает пустым.
```
#### Формат вывода
```
Верните голову списка, в котором удален нужный элемент.
```
</details>

---

<details>
<summary>
<strong>Заботливая мама</strong>
</summary><br>

[`Решение`](/sprint_2/4_carefulMom.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/D/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107665701/)
```
Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей: 
напишите функцию solution, определяющую индекс первого вхождения передаваемого
ей на вход значения в связном списке, если значение присутствует.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать 
только функцию, которая принимает на вход голову списка и искомый элемент, 
а возвращает целое число — индекс найденного элемента или -1.
```
#### Формат ввода
```
Функция на вход принимает голову односвязного списка и элемент, который нужно 
найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым.
```
#### Формат вывода
```
Функция возвращает индекс первого вхождения искомого элемента в список
(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.
```
</details>

---

<details>
<summary>
<strong>Всё наоборот</strong>
</summary><br>

[`Решение`](/sprint_2/5_inOpposite.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/E/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107673855/)
```
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел 
теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список 
в обратном порядке.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать 
только функцию, которая принимает на вход голову двусвязного списка и 
возвращает голову перевёрнутого списка. Ниже дано описание структуры, которая 
задаёт вершину списка.
```
#### Формат ввода
```
Функция принимает на вход единственный аргумент — голову двусвязного списка.
Длина списка не превосходит 1000 элементов. Список не бывает пустым.
```
#### Формат вывода
```
Функция должна вернуть голову развернутого списка.
```
</details>

---

<details>
<summary>
<strong>Стек - Max</strong>
</summary><br>

[`Решение`](/sprint_2/6_stackMax.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/F/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107676742/)
```
Нужно реализовать класс StackMax, который поддерживает операцию определения 
максимума среди всех элементов в стеке. Класс должен поддерживать 
операции push(x), где x – целое число, pop() и get_max().
```
#### Формат ввода
```
В первой строке записано одно число n — количество команд, которое не 
превосходит 10000. В следующих n строках идут команды. Команды могут быть 
следующих видов:
 - push(x) — добавить число x в стек;
 - pop() — удалить число с вершины стека;
 - get_max() — напечатать максимальное число в стеке;
Если стек пуст, при вызове команды get_max() нужно напечатать «None», для 
команды pop() — «error».
```
#### Формат вывода
```
Для каждой команды get_max() напечатайте результат её выполнения. Если стек 
пустой, для команды get_max() напечатайте «None». Если происходит удаление из 
пустого стека — напечатайте «error».
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        8<br>
        get_max<br>
        push 7<br>
        pop<br>
        push -2<br>
        push -1<br>
        pop<br>
        get_max<br>
        get_max<br>
    </td>
    <td valign="top">
        None<br>
        -2<br>
        -2<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Стек - MaxEffective</strong>
</summary><br>

[`Решение`](/sprint_2/7_stackMaxEffective.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/G/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/107700525/)
```
Реализуйте класс StackMaxEffective, поддерживающий операцию
определения максимума среди элементов в стеке.
Сложность операции должна быть O(1).
Для пустого стека операция должна возвращать None.
При этом push(x) и pop() также должны выполняться за константное время.
```
#### Формат ввода
```
В первой строке записано одно число — количество команд,
оно не превосходит 100000. Далее идут команды по одной в строке.
Команды могут быть следующих видов:
push(x) — добавить число x в стек. Число x не превышает 105;
pop() — удалить число с вершины стека;
get_max() — напечатать максимальное число в стеке;
top() — напечатать число с вершины стека;
Если стек пуст, при вызове команды get_max нужно напечатать «None»,
для команды pop и top — «error».
```
#### Формат вывода
```
Для каждой команды get_max() напечатайте результат её выполнения.
Если стек пустой, для команды get_max() напечатайте «None».
Если происходит удаление из пустого стека — напечатайте «error».
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        13<br>
pop<br>
pop<br>
top<br>
push 4<br>
push -5<br>
top<br>
push 7<br>
pop<br>
pop<br>
get_max<br>
top<br>
pop<br>
get_max
    </td>
    <td valign="top">
       error<br>
error<br>
error<br>
-5<br>
4<br>
4<br>
None
    </td>
  </tr>
</tbody></table>

</details>

---


<details>
<summary>
<strong>Скобочная последовательность</strong>
</summary><br>

 [`Решение`](/sprint_2/8_bracketSequence.js) | [`Условие`](https://contest.yandex.ru/contest/23758/problems/H/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/110803448/)
```
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. 
Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно 
популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
 - пустая строка —– правильная скобочная последовательность;
 - правильная скобочная последовательность, взятая в скобки одного 
типа, –— правильная скобочная последовательность;
 - правильная скобочная последовательность с приписанной слева или справа 
правильной скобочной последовательностью —– тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}.
Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную 
последовательность и возвращает True, если последовательность правильная, 
а иначе False.
```
#### Формат ввода
```
На вход подаётся одна строка, содержащая скобочную последовательность. 
Скобки записаны подряд, без пробелов.
```
#### Формат вывода
```
Выведите «True» или «False».
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        {[()]}<br>
    </td>
    <td valign="top">
        True<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Ограниченная очередь</strong>
</summary><br>

[`Решение`](/sprint_2/9_limitedQueue.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/I/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/108124460/)
```
Астрологи объявили день очередей ограниченного размера. Тимофею нужно 
написать класс MyQueueSized, который принимает параметр max_size, означающий 
максимально допустимое количество элементов в очереди.
Помогите ему —– реализуйте программу, которая будет эмулировать работу такой 
очереди. Функции, которые надо поддержать, описаны в формате ввода.
```
#### Формат ввода
```
В первой строке записано одно число — количество команд, оно не превосходит 5000.
Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000.
Далее идут команды по одной на строке. Команды могут быть следующих видов:

 - push(x) — добавить число x в очередь;
 - pop() — удалить число из очереди и вывести на печать;
 - peek() — напечатать первое число в очереди;
 - size() — вернуть размер очереди;
При превышении допустимого размера очереди нужно вывести «error». 
При вызове операций pop() или peek() для пустой очереди нужно вывести «None».
```
#### Формат вывода
```
Напечатайте результаты выполнения нужных команд, по одному на строке.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        8<br>
        2<br>
        peek<br>
        push 5<br>
        push 2<br>
        peek<br>
        size<br>
        size<br>
        push 1<br>
        size<br>
    </td>
    <td valign="top">
        None<br>
        5<br>
        2<br>
        2<br>
        error<br>
        2<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Списочная очередь</strong>
</summary><br>

[`Решение`](/sprint_2/10_listedQueue.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/J/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/108135114/)
```
Любимый вариант очереди Тимофея — очередь, написанная с использованием 
связного списка. Помогите ему с реализацией. Очередь должна поддерживать 
выполнение трёх команд:

 - get() — вывести элемент, находящийся в голове очереди, и удалить его.
Если очередь пуста, то вывести «error».
 - put(x) — добавить число x в очередь
 - size() — вывести текущий размер очереди
```
#### Формат ввода
```
В первой строке записано количество команд n — целое число, не превосходящее 
1000. В каждой из следующих n строк записаны команды по одной строке.
```
#### Формат вывода
```
Выведите ответ на каждый запрос по одному в строке.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        10<br>
        put -34<br>
        put -23<br>
        get<br>
        size<br>
        get<br>
        size<br>
        get<br>
        get<br>
        put 80<br>
        size<br>
    </td>
    <td valign="top">
        -34<br>
        1<br>
        -23<br>
        0<br>
        error<br>
        error<br>
        1<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Рекурсивные числа Фибоначчи</strong>
</summary><br>

[`Решение`](/sprint_2/11_recursiveFibbonachi.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/K/) | [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/108147214/)
```
У Тимофея было n(0≤n≤32) стажёров. Каждый стажёр хотел быть лучше своих 
предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали 
два предыдущих стажёра в сумме. Два первых стажёра были менее 
инициативными —– они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). 
Тогда выполняется следующее: F0=F1=1. Для всех i≥2 выполнено Fi=F(i−1)+F(i−2).
Определите, сколько кода напишет следующий стажёр –— найдите Fn.
Решение должно быть реализовано рекурсивно.
```
#### Формат ввода
```
На вход подаётся n — целое число в диапазоне от 0 до 32.
```
#### Формат вывода
```
Нужно вывести Fn.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        3<br>
    </td>
    <td valign="top">
        3<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Фибоначчи по модулю</strong>
</summary><br>

 [`Решение`](/sprint_2/12_fibModule.js) | [`Условие`](https://contest.yandex.ru/contest/22779/problems/L/) |  [`Отчет`](https://contest.yandex.ru/contest/22779/run-report/110803040/)
```
У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 10^6) человек. Каждый 
стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал 
столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых 
стажёра были менее инициативными — они сделали по одному коммиту.

Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). 
Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i≥ 2 
выполнено Fi=Fi−1+Fi−2.
Определите, сколько кода напишет следующий стажёр –— найдите последние k цифр 
числа Fn.
**Как найти k последних цифр**,
Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток 
от его деления на число 10k. Эта операция обозначается как x mod 10k. 
Узнайте, как записывается операция взятия остатка по модулю в вашем языке 
программирования.
Также обратите внимание на возможное переполнение целочисленных типов, если в 
вашем языке такое случается.
#### Формат ввода
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 10^6) 
и k (1 ≤ k ≤ 8).
```
#### Формат вывода
```
Выведите единственное число – последние k цифр числа Fn.
Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        3 1<br>
    </td>
    <td valign="top">
        3<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Дек | Финальная задача №1</strong>
</summary><br>

[`Решение`](/sprint_2/finals/taskA.js) | [`Условие`](https://contest.yandex.ru/contest/22781/problems/A/) | [`Отчет`](https://contest.yandex.ru/contest/22781/run-report/108230804/)
```
Гоша реализовал структуру данных Дек, максимальный размер которого определяется 
заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() 
работали корректно. Но, если в деке было много элементов, программа работала 
очень долго. Дело в том, что не все операции выполнялись за O(1). 
Помогите Гоше! Напишите эффективную реализацию.
**Внимание: при реализации используйте кольцевой буфер.**
```
#### Формат ввода
```
В первой строке записано количество команд n — целое число, не превосходящее 
100000. Во второй строке записано число m — максимальный размер дека. Он не 
100001. превосходит 50000. В следующих n строках записана одна из команд:

 - push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».
 - push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».
 - pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».
 - pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».
Value — целое число, по модулю не превосходящее 1000.
```
#### Формат вывода
```
Выведите результат выполнения каждой команды на отдельной строке. Для успешных 
запросов push_back(x) и push_front(x) ничего выводить не надо.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        4<br>
        4<br>
        push_front 861<br>
        push_front -819<br>
        pop_back<br>
        pop_back<br>
    </td>
    <td valign="top">
        861<br>
        -819<br>
    </td>
  </tr>
</tbody></table>

</details>

---

<details>
<summary>
<strong>Калькулятор | Финальная задача №2</strong>
</summary><br>

[`Решение`](/sprint_2/finals/taskB.js) | [`Условие`](https://contest.yandex.ru/contest/22781/problems/B/) | [`Отчет`](https://contest.yandex.ru/contest/22781/run-report/108230984/)

```
Задание связано с обратной польской нотацией. Она используется для парсинга 
арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.

Пример 1:
3 4 +
означает 3 + 4 и равно 7

Пример 2:
12 5 /
Так как деление целочисленное, то в результате получим 2.

Пример 3:
10 2 4 * -
означает 10 - 2 * 4 и равно 2

Разберём последний пример подробнее:
Знак * стоит сразу после чисел 2 и 4, значит к ним нужно применить операцию, которую этот знак обозначает, то есть перемножить эти два числа. В результате получим 8.
После этого выражение приобретёт вид:

10 8 -

Операцию «минус» нужно применить к двум идущим перед ней числам, то есть 10 и 8. В итоге получаем 2.
Рассмотрим алгоритм более подробно. Для его реализации будем использовать стек.
Для вычисления значения выражения, записанного в обратной польской нотации, нужно считывать выражение слева направо и придерживаться следующих шагов:
 1. Обработка входного символа:
   - Если на вход подан операнд, он помещается на вершину стека.
   - Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека.
 2. Если входной набор символов обработан не полностью, перейти к шагу 1. 
 3. После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент.
**Замечание про отрицательные числа и деление:** в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.

Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.

В текущей задаче гарантируется, что деления на отрицательное число нет.
```
#### Формат ввода
```
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.
На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.
Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
```
#### Формат вывода
```
Выведите единственное число — значение выражения.
```
#### Пример
<table><tbody>
  <tr>
    <td><b>Ввод</b></td>
    <td><b>Вывод</b></td>
  </tr>
  <tr>
    <td valign="top">
        2 1 + 3 *<br>
    </td>
    <td valign="top">
        9<br>
    </td>
  </tr>
</tbody></table>

</details>

---
